<?php 
/*
parameters:
	1st string
	2nd string
	(opt) int bonus for gap (default = -4)
	(opt) int bonus for match (default = 5)
	(opt) int bonus for mismatch (default = -3)
	(opt) boolean if true finds way according smallest number
methods:
	getComparedStrings()
		returns:
			$strings['string1']
			$strings['compare']
			$strings['string2']
	getPathScore()
	printPathMatrix()
	run($string1, $string2)
*/
Class GlobalAlignator {

	private $string1;
	private $string2;
	
	private $comparedString1 = "";
	private $comparedString2 = "";
	private $middleString = "";
	
	private $d; //gap bonus
	private $match;
	private $mismatch;
	
	private $matrixScore = array();
	private $matrixPath = array();
	
	private $pathScore;
	private $compared = false;
	private $reversed;
	
	function __construct($string1, $string2, $d=-4, $match=5, $mismatch=-3, $reversed=false) {
		$this->d = $d;
		$this->match = $match;
		$this->mismatch = $mismatch;
		$this->reversed = $reversed;
		
		$this->run($string1, $string2);
	}
	
	public function run($string1, $string2) {
		$this->resetVar();
		
		$this->string1 = '0'.$string1;
		$this->string2 = '0'.$string2;
		
		$this->makePath();
	}
	
	public function resetVar(){
		$this->string1 = null;
		$this->string2 = null;
		
		$this->comparedString1 = "";
		$this->comparedString2 = "";
		$this->middleString = "";
		
		$this->matrixScore = array();
		$this->matrixPath = array();
		
		$this->pathScore = null;
		$this->compared = false;
	}
	
	private function initScoreMatrix(){
		$this->matrixScore = array(
			'A' => array('A'=>$this->match,'C'=>$this->mismatch,'T'=>$this->mismatch,'G'=>$this->mismatch),
			'C' => array('A'=>$this->mismatch,'C'=>$this->match,'T'=>$this->mismatch,'G'=>$this->mismatch),
			'T' => array('A'=>$this->mismatch,'C'=>$this->mismatch,'T'=>$this->match,'G'=>$this->mismatch),
			'G' => array('A'=>$this->mismatch,'C'=>$this->mismatch,'T'=>$this->mismatch,'G'=>$this->match)
		);
	}
	
	//create matrix with best path velues and stores final path index 
	private function makePath() {
		if (empty($this->matrixScore))
			$this->initScoreMatrix();
		
		for($i=0; $i < strlen($this->string2); $i++) {
			for($j=0; $j < strlen($this->string1); $j++) {
				if ($i == 0 && $j==0)
					$this->matrixPath[$i][$j] = 0;
				//first horizontal row
				elseif ($i == 0)
					$this->matrixPath[$i][$j] = $this->matrixPath[$i][$j-1] + $this->d;
				//first vertical row
				elseif ($j == 0)
					$this->matrixPath[$i][$j] = $this->matrixPath[$i-1][$j] + $this->d;
				else {
					//vertical gap
					$a = $this->matrixPath[$i-1][$j] + $this->d;
					//horizontal gap
					$b = $this->matrixPath[$i][$j-1] + $this->d;
					//no gap
					$c =  $this->matrixPath[$i-1][$j-1] + $this->matrixScore[$this->string2{$i}][$this->string1{$j}];
					
					if($this->reversed)
						$this->matrixPath[$i][$j] = min($a, $b, $c);
					else
						$this->matrixPath[$i][$j] = max($a, $b, $c);
				}
			}
		}
		//for-cycle ends with indexes +1
		$this->pathScore = $this->matrixPath[$i-1][$j-1];
	}
	
	//finds the optimal path through matrix and saves the string alignment
	private function compare(){
		if (is_null($this->pathScore))
			$this->makePath();
		
		$i = count($this->matrixPath)-1;
		$j = count($this->matrixPath[0])-1;
		
		while ($i >= 0 && $j >= 0) {
			$a = $this->string1{$j};
			$b = $this->string2{$i};
			
			//the very left of the matrix 
			if ($j == 0) {
				//get rid of leading zero
				if ($i!=0) {
					$this->comparedString1 = " ".$this->comparedString1;
					$this->comparedString2 = $b.$this->comparedString2;
					$this->middleString = " ".$this->middleString;
				}
				$i--;
			}
			//the very top of the matrix
			elseif($i==0) {
				//get rid of leading zero
				if($j!=0) {
					$this->comparedString1 = $a.$this->comparedString1;
					$this->comparedString2 = " ".$this->comparedString2;
					$this->middleString = " ".$this->middleString;
				}
				$j--;
			}
			else {
				$num = $this->matrixPath[$i][$j];
				$iNum = $this->matrixPath[$i][$j-1];
				$jNum = $this->matrixPath[$i-1][$j];
				
				if ($this->reversed) {
					$moveLeft = ($iNum < $jNum) && ($iNum < $num);
					$moveTop = ($jNum < $iNum) && ($jNum < $num);
				}
				else {
					$moveLeft = ($iNum > $jNum) && ($iNum > $num);
					$moveTop = ($jNum > $iNum) && ($jNum > $num);
				}
				
				//move horizontal
				if ($moveLeft) {
					$this->comparedString1 = $a.$this->comparedString1;
					$this->comparedString2 = "-".$this->comparedString2;
					$this->middleString = " ".$this->middleString;
					$j--;
				}
				//move vertical
				elseif ($moveTop) {
					$this->comparedString1 = "-".$this->comparedString1;
					$this->comparedString2 = $b.$this->comparedString2;
					$this->middleString = " ".$this->middleString;
					$i--;
				}
				//move diagonal
				else{
					$this->comparedString2 = $b.$this->comparedString2;
					$this->comparedString1 = $a.$this->comparedString1;
					
					if ($a==$b)
						$this->middleString = "|".$this->middleString;
					else
						$this->middleString = " ".$this->middleString;
						
					$i--;
					$j--;
				}
			}
		}
		$this->compared = true;
	}
	
	public function getScoreMatrix(){
		return $this->matrixScore;
	}
	
	public function getPathMatrix(){
		return $this->matrixPath;
	}
	
	public function printPathMatrix(){
		echo "<pre>";
		
		for($i=0; $i < count($this->matrixPath); $i++) {
			for($j=0; $j < count($this->matrixPath[$i]); $j++) {
				echo $this->matrixPath[$i][$j]."\t";
			}
			echo "\n";
		}
		echo "<pre>";
	}
	
	public function getPathScore() {
		return $this->pathScore;
	}
	
	public function getComparedStrings(){
		if (!$this->compared)
			$this->compare();
		
		return array(
			"string1" => $this->comparedString1,
			"string2" => $this->comparedString2,
			"compare" => $this->middleString
		);
	}
}
?>
